package b_sorting_advance;

import b_sorting_advance.a_merge_sort.MergeSort;
import b_sorting_advance.a_merge_sort.MergeSortBottomUp;
import b_sorting_advance.b_quick_sort.QuickSorting2Ways;
import b_sorting_advance.b_quick_sort.QuickSorting3Ways;
import b_sorting_advance.c_heap_sort.HeapSorting;
import org.junit.Test;
import utils.ArrayGeneric;
import utils.sorting_helper.SortingHelper;

/**
 * @Author: DeLucia
 * @Description:
 * @Date: 2019/1/22 22:05.
 * <p>
 * 结论
 *
 *              平均时间复杂度     最好时间复杂度     最坏时间复杂度     是否原地排序      额外空间        是否是稳定排序
 *  选择排序    O(n^2)              O(n^2)          O(n^2)          Y               O(1)            N
 *  冒泡排序    O(n^2)              O(n)            O(n^2)          Y               O(1)            Y
 *  插入排序    O(n^2)              O(n)            O(n^2)          Y               O(1)            Y
 *  希尔排序    O(n^1.3)            O(n)            O(n^2)          Y               O(1)            N
 *  归并排序    O(nlogn)            O(nlogn)        O(nlogn)        N               O(n)            Y
 *  快速排序    O(nlogn)            O(nlogn)        O(n^2)(单路时)   Y               O(logn)         N
 *  堆排序      O(nlogn)            O(nlogn)        O(nlogn)        Y               O(1)            N
 *
 *  注：
 *  1. logn 均是 底数为2时的情况
 *  2. 稳定排序是指: 比较相等的元素经过排序后的相对位置是否维持原来的次序
 *  3. 一般如果要保证稳定性 一般选择归并排序， 而如果可以不保证稳定性 插入排序 是更佳选择
 *     如果避免排序的不稳定性？
 *     那就是自定义比较函数，制定比较规则，减少经过比较相等的情况，比如比较学生时，先比较成绩
 *     如果成绩相等再比较姓名字母序，如果姓名一样再比较出生日期等等。。消灭相等情况即可
 *  4. 如果排序过程不依赖临时空间，视为原地排序
 *  5. 额外空间，用到分治法递归的有归并排序和快速排序，平均递归深度时logn，因此需要logn的栈空间存储
 *     所以快速排序所需额外空间时logn
 *     而归并排序还需要n的临时空间因此 归并排序 所需额外空间时 O(n + logn) 当数据规模无限大时logn可以忽略 因此是 -> O(n)
 *  6. 然后目前并没有任何算法可以满足所有情况都是最优的，理论上应该有，但还没有被创造出来。
 *
 * 测试一：面临大量无序元素时，快速排序最佳。
 * 测试二：面临近乎有序数组时，归并排序最佳。
 * 测试三：面临包含大量重复元素数组的情况下，三路快速排序比归并排序、快速排序有质变的超越！
 * 总体而言，快速排序的性能是要优于归并排序！一般系统级别的快速排序都会选择三路快速排序，因为它在处理包含大量重复元素时，性能极高，即使不是，它的性能也得到保证，不会太差。
 *
 * idea开启断言测试
 * 在run>edit config> vm option中键入 -ea
  */
public class MainTest {

    public static void main(String[] args) throws CloneNotSupportedException {

        int numbers = 2000000; // 数据规模

        System.out.println("=================完全乱序=================");
        // 完全乱序
        // new InsertionSort().testSorting("插入排序", ArrayGeneric.getRandomIntegerArray(numbers, 0, numbers));
        new MergeSort().testSorting("归并排序", MergeSort.getRandomIntegerArray(numbers, 0, numbers));// 远胜于插入排序
        new QuickSorting2Ways().testSorting("随机基准双路快速排序", QuickSorting2Ways.getRandomIntegerArray(numbers, 0, numbers));
        new QuickSorting3Ways().testSorting("随机基准三路快速排序", QuickSorting3Ways.getRandomIntegerArray(numbers, 0, numbers));
        new HeapSorting().testSorting("堆原地排序", HeapSorting.getRandomIntegerArray(numbers, 0, numbers));

        System.out.println("=================接近有序=================");

        // 近乎有序
        int swapTimes = 10;
        // new InsertionSort().testNearlySorting("插入排序", ArrayGeneric.getNearlySortedIntegerArray(numbers, swapTimes));
        new MergeSort().testNearlySorting("归并排序", MergeSort.getNearlySortedIntegerArray(numbers, swapTimes));// 略逊于插入排序
        new QuickSorting2Ways().testNearlySorting("随机基准双路快速排序", QuickSorting2Ways.getNearlySortedIntegerArray(numbers, swapTimes)); //
        new QuickSorting3Ways().testNearlySorting("随机基准三路快速排序", QuickSorting3Ways.getNearlySortedIntegerArray(numbers, swapTimes)); //
        new HeapSorting().testNearlySorting("堆原地排序", HeapSorting.getNearlySortedIntegerArray(numbers, swapTimes)); //

        System.out.println("=================多数重复=================");
        // 包含大量重复元素
        // new InsertionSort().testSorting("插入排序", ArrayGeneric.getRandomIntegerArray(numbers, 0, 10));
        new MergeSort().testSorting("归并排序", MergeSort.getRandomIntegerArray(numbers, 0, 10));// 略逊于插入排序
        new QuickSorting2Ways().testSorting("随机基准双路快速排序", QuickSorting2Ways.getRandomIntegerArray(numbers, 0, 10)); //
        new QuickSorting3Ways().testSorting("随机基准三路快速排序",QuickSorting3Ways.getRandomIntegerArray(numbers, 0, 10));
        new HeapSorting().testSorting("堆原地排序",HeapSorting.getRandomIntegerArray(numbers, 0, 10));

        //        =================完全乱序=================
        //        归并排序 on 2000000 integer numbers		duration -> 1138ms
        //        随机基准双路快速排序 on 2000000 integer numbers		duration -> 673ms
        //        随机基准三路快速排序 on 2000000 integer numbers		duration -> 980ms
        //        堆原地排序 on 2000000 integer numbers		duration -> 2186ms
        //                =================接近有序=================
        //        归并排序 on nearly ordered 2000000 integer numbers		duration -> 90ms
        //        随机基准双路快速排序 on nearly ordered 2000000 integer numbers		duration -> 133ms
        //        随机基准三路快速排序 on nearly ordered 2000000 integer numbers		duration -> 311ms
        //        堆原地排序 on nearly ordered 2000000 integer numbers		duration -> 375ms
        //                =================多数重复=================
        //        归并排序 on 2000000 integer numbers		duration -> 399ms
        //        随机基准双路快速排序 on 2000000 integer numbers		duration -> 197ms
        //        随机基准三路快速排序 on 2000000 integer numbers		duration -> 66ms
        //        堆原地排序 on 2000000 integer numbers		duration -> 328ms

    }
}
